前言

今天來做九月每日挑戰的今天這題1328. Break a Palindrome。這題不是考驗程式能力，而是邏輯問題XD 歸納完規則的瞬間即可解題~

想法

我是先依照我的想法解題，後來官方解其實有更好的解法，如果不想繞遠路可以直接拉到下面優化解~

初始解法

所謂Palindrome在leetcode真的超級常出現，中文是"回文"，就是對稱的string，正著跟倒著會一樣，例如abcba或 元智幼稚園 (一時只能想到這個舉例QQ 無惡意)

順到一提，leetcode基礎題檢查是否為palindrome的作弊python3解法就是if(s==s[::-1])秒解XD

總之這題就是有一個原為回文的string，要在只改一個字的情況下且是字母順最小的情況下破壞這個回文，如果怎麼改都不行就回傳空字串。那我們就可以開始整理規則了：

1. 什麼情況下會怎麼改都不行?
   A: 只有在字串只有1個字的時候會怎麼改都不行
2. 可以改的情況下要怎麼讓字母順序最小?
   A: 第一個字改成'a'
3. 什麼情況下第一個字改成'a'不成立? 要怎麼改?
   A: 第一個字本來就是'a'的時候第一個字改成'a'沒用；就往後去改第一個不是'a'的字母，但若字串是單數的話正中間的改了也沒用。
4. 如果都不能改成'a'的情況下要怎麼改?
   A: 把最後一個字改成'b'就一定可以。
   接下來就是把以上的規則直接翻譯成程式就好了：

class Solution {
public:
    string breakPalindrome(string palindrome) {
        // check if impossible
        int l=palindrome.length();
        if(l==1){
            return "";
        }
        // turn the first one to 'a' if the first is not 'a'
        if(palindrome[0]!='a'){
            return "a"+palindrome.substr(1,l-1);
        }
        // the first one is a, check if there are no a characters
        for(int i=1;i<l;++i){
            // not a and not the middle one in odd string
            if(palindrome[i]!='a' && (l%2==0 || i!=l/2)){
                return palindrome.substr(0,i)+"a"+palindrome.substr(i+1,l-1-i);
            }
        }
            
        // otherwise, change the last one to b
        return palindrome.substr(0,l-1)+"b";
    }
};

感覺比起其他題目輕鬆簡單許多，題目下面有個留言蠻好笑的:

從這個問題領悟到的人生哲學: 破壞比修理一個東西簡單很多?

優化解

按照我的邏輯寫完之後，看到官方其實也有提供solution，才發現有可以優化之處：

1. 檢查是不是能改成'a'只需要檢查前半段就好，連判斷是不是中間點也不用了。因為原本是回文，所以如果前半都是a，後半也肯定都是a，結案。
2. 不需要用substr，直接用palindrome[i]去修改那個位置就好了。會沒用這樣改純粹是寫python寫習慣了XD python的string不能這樣改。

依據以上兩點改完之後程式就變得簡潔許多了：

class Solution {
public:
    string breakPalindrome(string palindrome) {
        // check if impossible
        int l=palindrome.length();
        if(l==1){
            return "";
        }
        // check if there are no a characters
        for(int i=0;i<l/2;++i){
            if(palindrome[i]!='a'){
                palindrome[i]='a';
                return palindrome;
            }
        }
        // otherwise, change the last one to b
        palindrome[l-1]='b';
        return palindrome;
    }
};

時間複雜度是O(n)，因為只需要遍歷前半段1/2*n就好了。

結語

每次寫完之後看看別人的解答，就有機會找到沒注意到的地方，下次就知道有什麼更好的寫法可以用了，共勉之(?)